home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Games / MacGnuGo 0.5e / gnugo.src / fiot.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-28  |  9.4 KB  |  309 lines  |  [TEXT/R*ch]
  1. #include "comment.header"
  2. extern unsigned char p[19][19], l[19][19];
  3. extern int MAXX, MAXY;
  4. extern int currentStone, opposingStone;
  5. extern long int rd;
  6. extern int lastMove;
  7.  
  8. /* don't make moves inside territory of chains with 2 eyes */
  9.  
  10. /*
  11.   t    mark all enclosed territories with a unique number
  12.   t1    mark all enclosed territories again
  13.   tc    mark a territory if it includes a corner
  14.   trs    mark territories owned by one side ( + current , - opponent )
  15.   cn    mark all chains
  16.   csafe    mark chains touching 2 owned territories
  17.   csize mark size of chains
  18.   tsize mark size of territories
  19.   tsafe    mark size of territories enclosed by safe chains
  20. */
  21.  
  22. static int t[19][19];        /* any territory */
  23. static int t1[19][19];        /* any territory */
  24. static int tc[19][19];        /* any territory */
  25. static int trs[19][19];        /* surrounded territory */
  26. static int cn[19][19];        /* chains */
  27. static int csize[19][19];    /* size of chains */
  28. static int csafe[19][19];    /* safe chains */
  29. static int tsize[19][19];    /* territory size */
  30. static int tsafe[19][19];    /* safe territory */
  31. static int ttime[19][19];    /* when was it safe/ */
  32. static int numt, c1, o1, a1, minlib1;
  33.  
  34. static void setmin1(int n) { if (n < minlib1) minlib1 = n; }
  35.  
  36. static void mter(int i, int j, int n)
  37. {
  38.   t[i][j] = n;
  39.   if (i > 0 && t[i-1][j] == 0 && p[i-1][j] == 0) mter(i-1,j,n);
  40.   if (i < MAXX-1 && t[i+1][j] == 0 && p[i+1][j] == 0) mter(i+1,j,n);
  41.   if (j > 0 && t[i][j-1] == 0 && p[i][j-1] == 0) mter(i,j-1,n);
  42.   if (j < MAXY-1 && t[i][j+1] == 0 && p[i][j+1] == 0) mter(i,j+1,n);
  43.   if (i > 0 && t[i-1][j] == 0 && p[i-1][j] == currentStone) o1 = 0;
  44.   if (i < MAXX-1 && t[i+1][j] == 0 && p[i+1][j] == currentStone) o1 = 0;
  45.   if (j > 0 && t[i][j-1] == 0 && p[i][j-1] == currentStone) o1 = 0;
  46.   if (j < MAXY-1 && t[i][j+1] == 0 && p[i][j+1] == currentStone) o1 = 0;
  47.   if (i > 0 && t[i-1][j] == 0 && p[i-1][j] == opposingStone) c1 = 0;
  48.   if (i < MAXX-1 && t[i+1][j] == 0 && p[i+1][j] == opposingStone) c1 = 0;
  49.   if (j > 0 && t[i][j-1] == 0 && p[i][j-1] == opposingStone) c1 = 0;
  50.   if (j < MAXY-1 && t[i][j+1] == 0 && p[i][j+1] == opposingStone) c1 = 0;
  51.   if (i > 0 && t[i-1][j] == 0 && p[i-1][j] != 0) setmin1(l[i-1][j]);
  52.   if (i < MAXX-1 && t[i+1][j] == 0 && p[i+1][j] != 0) setmin1(l[i+1][j]);
  53.   if (j > 0 && t[i][j-1] == 0 && p[i][j-1] != 0) setmin1(l[i][j-1]);
  54.   if (j < MAXY-1 && t[i][j+1] == 0 && p[i][j+1] != 0) setmin1(l[i][j+1]);
  55. }
  56.  
  57. static void mts(int i, int j, int n)
  58. {
  59.   t1[i][j] = n;
  60.   if (i > 0 && t1[i-1][j] == 0 && p[i-1][j] == 0) mts(i-1,j,n);
  61.   if (i < MAXX-1 && t1[i+1][j] == 0 && p[i+1][j] == 0) mts(i+1,j,n);
  62.   if (j > 0 && t1[i][j-1] == 0 && p[i][j-1] == 0) mts(i,j-1,n);
  63.   if (j < MAXY-1 && t1[i][j+1] == 0 && p[i][j+1] == 0) mts(i,j+1,n);
  64.   if (trs[i][j] != 0) {
  65.     if (i > 0 && csafe[i-1][j] > 0) a1 = 1;
  66.     if (i < MAXX-1 && csafe[i+1][j] > 0) a1 = 1;
  67.     if (j > 0 && csafe[i][j-1] > 0) a1 = 1;
  68.     if (j < MAXY-1 && csafe[i][j+1] > 0) a1 = 1;
  69.   }
  70. }
  71.  
  72. static void mcn(int i, int j, int n)
  73. {
  74.   int a;
  75.  
  76.   a = p[i][j];
  77.   cn[i][j] = n;
  78.   if (i > 0 && cn[i-1][j] == 0 && p[i-1][j] == a) mcn(i-1,j,n);
  79.   if (i < MAXX-1 && cn[i+1][j] == 0 && p[i+1][j] == a) mcn(i+1,j,n);
  80.   if (j > 0 && cn[i][j-1] == 0 && p[i][j-1] == a) mcn(i,j-1,n);
  81.   if (j < MAXY-1 && cn[i][j+1] == 0 && p[i][j+1] == a) mcn(i,j+1,n);
  82.  
  83.   if (a == currentStone && a1 > -1) {
  84.     if (i > 0 && p[i-1][j] == 0 && trs[i-1][j] > 0 && t[i-1][j] != a1)
  85.       { if (a1 == 0) a1 = t[i-1][j]; else a1 = -1; }
  86.     if (i < MAXX-1 && p[i+1][j] == 0 && trs[i+1][j] > 0 && t[i+1][j] != a1)
  87.       { if (a1 == 0) a1 = t[i+1][j]; else a1 = -1; }
  88.     if (j > 0 && p[i][j-1] == 0 && trs[i][j-1] > 0 && t[i][j-1] != a1)
  89.       { if (a1 == 0) a1 = t[i][j-1]; else a1 = -1; }
  90.     if (j < MAXY-1 && p[i][j+1] == 0 && trs[i][j+1] > 0 && t[i][j+1] != a1)
  91.       { if (a1 == 0) a1 = t[i][j+1]; else a1 = -1; }
  92.   }
  93.  
  94.   if (a == opposingStone && a1 > -1) {
  95.     if (i > 0 && p[i-1][j] == 0 && trs[i-1][j] < 0 && t[i-1][j] != a1)
  96.       { if (a1 == 0) a1 = t[i-1][j]; else a1 = -1; }
  97.     if (i < MAXX-1 && p[i+1][j] == 0 && trs[i+1][j] < 0 && t[i+1][j] != a1)
  98.       { if (a1 == 0) a1 = t[i+1][j]; else a1 = -1; }
  99.     if (j > 0 && p[i][j-1] == 0 && trs[i][j-1] < 0 && t[i][j-1] != a1)
  100.       { if (a1 == 0) a1 = t[i][j-1]; else a1 = -1; }
  101.     if (j < MAXY-1 && p[i][j+1] == 0 && trs[i][j+1] < 0 && t[i][j+1] != a1)
  102.       { if (a1 == 0) a1 = t[i][j+1]; else a1 = -1; }
  103.   }
  104. }
  105.  
  106. static void copytrs(int n, int v)
  107. {
  108.   int i,j;
  109.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) 
  110.       if (t[i][j] == n) trs[i][j] = v;
  111. }
  112.  
  113. static void copycsafe(int n, int v)
  114. {
  115.   int i,j;
  116.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) 
  117.       if (cn[i][j] == n) csafe[i][j] = v;
  118. }
  119.  
  120. static void copytsafe(int n, int v)
  121. {
  122.   int i,j;
  123.   int m = 0;
  124.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) 
  125.       if (t1[i][j] == n) m++;
  126.   if (v < 0) m = -m;
  127.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) 
  128.       if (t1[i][j] == n) {
  129.     tsafe[i][j] = m;
  130.     ttime[i][j] = lastMove;
  131.       }
  132. }
  133.  
  134. void markcorners()
  135. {
  136.   int i,j,n;
  137.   if ((n = t[0][0]) != 0)
  138.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) if (t[i][j] == n) tc[i][j] = 2;
  139.   if ((n = t[0][MAXX-1]) != 0)
  140.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) if (t[i][j] == n) tc[i][j] = 2;
  141.   if ((n = t[0][MAXY-1]) != 0)
  142.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) if (t[i][j] == n) tc[i][j] = 2;
  143.   if ((n = t[MAXX-1][MAXY-1]) != 0)
  144.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) if (t[i][j] == n) tc[i][j] = 2;
  145. }
  146.  
  147. /* marks territory inside an eye (maybe a false eye though) */
  148.  
  149. void markt()
  150. {
  151.   int i,j,k,n,m;
  152.  
  153.   numt = 1;
  154.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) {
  155.     t[i][j] = 0; t1[i][j] = 0; tc[i][j] = 0; trs[i][j] = 0;
  156.     cn[i][j] = 0; csafe[i][j] = 0; csize[i][j] = 0;
  157.     tsize[i][j] = 0; tsafe[i][j] = 0; ttime[i][j] = -10;
  158.   }
  159.   for (i=0;i<MAXX;i++)
  160.     for (j=0;j<MAXY;j++) 
  161.       if (t[i][j] == 0 && p[i][j] == 0) {
  162.         o1 = 1;
  163.     c1 = 1;
  164.     minlib1 = 300;
  165.     mter(i,j,numt);
  166.     if (c1 && !o1) { copytrs(numt, minlib1); }
  167.     if (o1 && !c1) { copytrs(numt, -minlib1); }
  168.         numt++;
  169.       }
  170.   for (k=1;k<numt;k++) {
  171.     n = 0;
  172.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  173.       if (t[i][j] == k) n++;
  174.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  175.       if (t[i][j] == k) tsize[i][j] = n;
  176.   }
  177.   m = numt;
  178.   for (i=0;i<MAXX;i++)
  179.     for (j=0;j<MAXY;j++) 
  180.       if (cn[i][j] == 0 && p[i][j] != 0) {
  181.         a1 = 0;
  182.     mcn(i,j,numt);
  183.     if (a1 < 0) { copycsafe(numt, p[i][j]); }
  184.         numt++;
  185.       }
  186.   for (k=m;k<numt;k++) {
  187.     n = 0;
  188.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  189.       if (cn[i][j] == k) n++;
  190.     for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  191.       if (cn[i][j] == k) csize[i][j] = n;
  192.   }
  193.       
  194.   for (i=0;i<MAXX;i++)
  195.     for (j=0;j<MAXY;j++) 
  196.       if (t1[i][j] == 0 && trs[i][j] != 0) {
  197.     a1 = 0;
  198.     mts(i,j,numt);
  199.     if (a1 == 1) { copytsafe(numt, trs[i][j]); }
  200.     numt++;
  201.       }
  202.    markcorners();
  203. }
  204.  
  205. /* count number of stones surrounding a territory */
  206. static int countwall(int x, int y)
  207. {
  208.   int t2[19][19];    /* surrounding stones */
  209.   int i,j,n,m;
  210.   if (p[x][y] != 0) return(0);
  211.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) t2[i][j] = 0;
  212.   m = t[x][y];
  213.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  214.     if (t[i][j] == m) {
  215.       if (i > 0 && p[i-1][j] != 0) t2[i-1][j] = 1;
  216.       if (i < MAXX-1 && p[i+1][j] != 0) t2[i+1][j] = 1;
  217.       if (j > 0 && p[i][j-1] != 0) t2[i][j-1] = 1;
  218.       if (j < MAXY-1 && p[i][j+1] != 0) t2[i][j+1] = 1;
  219.     }
  220.   for (n=0,i=0;i<MAXX;i++) for (j=0;j<MAXY;j++)
  221.     if (t2[i][j] == 1) n++;
  222.   return(n);
  223. }
  224.  
  225. int throwin(int i, int j)
  226. {
  227.   if (csize[i][j] == 1 && ttime[i][j] > lastMove - 5) return (1);
  228.   else return (0);
  229. }
  230.  
  231. int locallibs(int i, int j)
  232. { int n = 0;
  233.   if (i > 0 && p[i-1][j] == 0) n++;
  234.   if (i < MAXX-1 && p[i+1][j] == 0) n++;
  235.   if (j > 0 && p[i][j-1] == 0) n++;
  236.   if (j < MAXY-1 && p[i][j+1] == 0) n++;
  237.   return(n);
  238. }
  239.  
  240. int getcsize(int i, int j) { return (csize[i][j]); }
  241.  
  242. int findsplitter(int *x, int *y)
  243. {
  244.   int i,j,n,val;
  245.   val = 0; *x = *y = -1;
  246.   for (i=0;i<MAXX;i++) for (j=0;j<MAXY;j++) {
  247.     if ( tsafe[i][j] == 0 &&
  248.          ( (trs[i][j] > 0 && tsize[i][j] >= 3) ||
  249.        (trs[i][j] < 0 && tsize[i][j] == 3) )) {
  250.       n = locallibs(i,j);
  251.       if (n > val) { val = n; *x = i; *y = j; }
  252.     }
  253.   }
  254.   return(val > 1);
  255. }
  256.  
  257. /* returns true if move is inside an eye (not too large an eye, though) */
  258.  
  259. #ifdef debug
  260. #include <stdio.h>
  261. int debug_dump() { int i,j; putchar('\n');
  262.   for (i = 0; i < MAXX; i++) {
  263.       for (j = 0; j < MAXY; j++) printf("%2d ",trs[i][j]);
  264.       putchar(';');
  265.       for (j = 0; j < MAXY; j++) printf("%2d ",tsize[i][j]);
  266.       putchar('\n'); }
  267.   putchar('\n');
  268. }
  269. #else
  270. int debug_dump() { return 0; }
  271. #endif
  272.  
  273. #define NOT_OK 1
  274. #define OK 0
  275.  
  276. /* return 1 if inside inside strong territory */
  277. int fiot(int i, int j, int k)
  278. {
  279.   int n,s;
  280. #ifdef debug
  281.   printf("%d %d; ",i,j);
  282. #endif
  283.   if (trs[i][j] == 0) return(OK);    /* not anybodies terrirory */
  284.   if (tsafe[i][j] > 0 && tsafe[i][j] <  9) return(NOT_OK); /* my eye */
  285.   if (tsafe[i][j] < 0 && tsafe[i][j] > -9) return(NOT_OK); /* opponent eye */
  286.   s = tsize[i][j];
  287.   if (locallibs(i,j) < 2) return(NOT_OK);
  288.   if (tsafe[i][j] != 0 && trs[i][j] > 0) {    /* my territory */
  289.     if (s < 3) return(NOT_OK);
  290.     n = countwall(i,j);
  291.     if (s > MAXX*MAXY/3) return(OK);
  292.     if (tc[i][j] == 2) {
  293.          if (n*n/4 > s) return(NOT_OK);    /* in the corner */
  294.     }
  295.     else if (n*n*n/27 > s) return(NOT_OK);
  296.   }
  297.   else if (trs[i][j] < 0) {            /* opponent territory */
  298.     if (tsafe[i][j] == 0 && tsize[i][j] <= 3) return(OK);
  299.     n = countwall(i,j);
  300.     if (tc[i][j] == 2) {
  301.          if (n*n/4 > s) return(NOT_OK);
  302.     }
  303.     else if (n*n*n/27 > s) return(NOT_OK);
  304.   }
  305.   return(OK);
  306. }
  307.  
  308. /* */
  309.